#include "include/pf_hash.h"
#include "include/pf_internal.h"

#include <stdio.h>
#include <stdlib.h>
#include <limits.h>

#define HASHTAB_MAX_NODES    0xffffffff

struct pf_hash_node
{
    union node_key
    {
        void*               ptr;
        uint64_t            num;
    }                       key;
    void*                   data;
    struct pf_hash_node*    next;
};

struct pf_hash
{
    /* hash function */
    uint32_t(*hash_value)(const void *key);

    /* key comparison function */
    int(*key_cmp)(const void *key1, const void *key2);

    uint32_t                slot_size;      /* number of slots in hash table */
    uint32_t                value_count;    /* number of elements in hash table */
    struct pf_hash_node*    htable[0];      /* hash table */
};

/*********************************************************************************************
Function Name:  get_table_size
Description  :  
Inputs       :  uint32_t size                    :  
Outputs      :  return value                     :   
ErrorCodes   :  
History      :
---------------------------------------------------------------------------------------------
Author                 Date                          Comments
zhanggp                2011-06-29                    create
**********************************************************************************************/
static inline uint32_t get_table_size(uint32_t size);

/*********************************************************************************************
Function Name:  find_num_impl
Description  :  
Inputs       :  const struct pf_hash* hash       :  
                uint64_t key                     :
                struct pf_hash_node** prev       :
Outputs      :  return value                     :   
ErrorCodes   :  
History      :
---------------------------------------------------------------------------------------------
Author                 Date                          Comments
zhanggp                2011-06-29                    create
**********************************************************************************************/
static inline struct pf_hash_node* find_num_impl(const struct pf_hash* hash, 
                                                 uint64_t key, 
                                                 struct pf_hash_node** prev);

/*********************************************************************************************
Function Name:  find_ptr_impl
Description  :  
Inputs       :  const struct pf_hash* hash       :  
                uint64_t key                     :
                struct pf_hash_node** prev       :
Outputs      :  return value                     :   
ErrorCodes   :  
History      :
---------------------------------------------------------------------------------------------
Author                 Date                          Comments
zhanggp                2011-06-29                    create
**********************************************************************************************/
static inline struct pf_hash_node* find_ptr_impl(const struct pf_hash* hash, 
                                                 void* key, 
                                                 struct pf_hash_node** prev);

/*********************************************************************************************
Function Name:  insert_impl
Description  :  
Inputs       :  const struct pf_hash* hash       :  
                uint64_t num                     :
                void* ptr                        :
                void* value                      :
                struct pf_hash_node* prev        :
Outputs      :  return value                     :   
ErrorCodes   :  
History      :
---------------------------------------------------------------------------------------------
Author                 Date                          Comments
zhanggp                2011-06-29                    create
**********************************************************************************************/
static inline int insert_impl(struct pf_hash* hash, 
                              uint64_t num, 
                              void* ptr, 
                              void* value, 
                              struct pf_hash_node* prev);

/*********************************************************************************************
Function Name:  erase_impl
Description  :  
Inputs       :  const struct pf_hash* hash       :  
                uint32_t hvalue                  :
                struct pf_hash_node* cur         :
                struct pf_hash_node* prev        :
Outputs      :  return value                     :   
ErrorCodes   :  
History      :
---------------------------------------------------------------------------------------------
Author                 Date                          Comments
zhanggp                2011-06-29                    create
**********************************************************************************************/
static inline void* erase_impl(struct pf_hash* hash, 
                               uint32_t hvalue,
                               struct pf_hash_node* cur, 
                               struct pf_hash_node* prev);

/********************************************************************************************/
 
struct pf_hash* pf_hash_create(uint32_t (*hash_value)(const void *key),
                               int (*key_cmp)(const void *key1, const void *key2),
                               uint32_t size)
{
    struct pf_hash* p = NULL;

    size = get_table_size(size);

    p = malloc(sizeof(struct pf_hash) + sizeof(struct pf_hash_node) * size);
    if(p == NULL)
    {
        pf_set_errno(PF_ENOMEM);
        return NULL;
    }

    p->slot_size = size;
    p->value_count = 0;
    p->hash_value = hash_value;
    p->key_cmp = key_cmp;
    memset(p->htable, 0x00, sizeof(struct pf_hash_node) * size);

    return p;
}

int pf_hash_destory(struct pf_hash* hash)
{
    assert(hash);

    pf_hash_clear(hash);
    free(hash);

    return 0;
}

/*********************************************************************************************
Function Name:  pf_hash_find_ptr
Description  :  find value by key
Inputs       :  struct pf_hash* hash                        :   The hash table
                void* key                                   :   The hash key
Outputs      :  return value                                :   The hash key 's value
ErrorCodes   :
History      :
---------------------------------------------------------------------------------------------
Author                 Date                          Comments
zhanggp                2011-06-29                    create
**********************************************************************************************/
void* pf_hash_find_ptr(const struct pf_hash* hash, void* key)
{
    struct pf_hash_node* cur = NULL;
    struct pf_hash_node* prev= NULL;

    assert(hash);
    assert(hash->hash_value);
    assert(hash->key_cmp);

    cur = find_ptr_impl(hash, key, &prev);
    if(cur == NULL)
    {
        pf_set_errno(PF_ENOKEY);
        return NULL;
    }

    return  cur->data;
}

void* pf_hash_find_num(const pf_hash_t* hash, uint64_t key)
{
    struct pf_hash_node* cur = NULL;
    struct pf_hash_node* prev= NULL;

    assert(hash);

    cur = find_num_impl(hash, key, &prev);
    if(cur == NULL)
    {
        pf_set_errno(PF_ENOKEY);
        return NULL;
    }

    return  cur->data;
}

int pf_hash_insert_ptr(struct pf_hash* hash,
                       void* key,
                       void* value)
{
    struct pf_hash_node* prev    = NULL;
    struct pf_hash_node* cur     = NULL;

    assert(hash);
    assert(hash->hash_value);
    assert(hash->key_cmp);

    if(hash->value_count == HASHTAB_MAX_NODES)
    {
        pf_set_errno(PF_EDQUOT);
        return PF_EDQUOT;
    }

    cur = find_ptr_impl(hash, key, &prev);
    if(cur)
    {
        pf_set_errno(PF_EKEYREJECTED);
        return PF_EKEYREJECTED;
    }

    return insert_impl(hash, hash->hash_value(key), key, value,  prev);
}

int pf_hash_insert_num(pf_hash_t* hash,
                       uint64_t key,
                       void* value)
{
    struct pf_hash_node* prev    = NULL;
    struct pf_hash_node* cur     = NULL;

    assert(hash);

    if(hash->value_count == HASHTAB_MAX_NODES)
    {
        pf_set_errno(PF_EDQUOT);
        return PF_EDQUOT;
    }

    cur = find_num_impl(hash, key, &prev);
    if(cur)
    {
        pf_set_errno(PF_EKEYREJECTED);
        return PF_EKEYREJECTED;
    }

    return insert_impl(hash, key, NULL, value,  prev);
}

void* pf_hash_erase_ptr(struct pf_hash* hash, void* key)
{
    struct pf_hash_node* cur  = NULL;
    struct pf_hash_node* prev = NULL;

    assert(hash);
    assert(hash->hash_value);
    assert(hash->key_cmp);

    cur = find_ptr_impl(hash, key, &prev);
    if(cur == NULL)
    {
        pf_set_errno(PF_ENOKEY);
        return NULL;
    }

    return erase_impl(hash, hash->hash_value(key) % hash->slot_size,cur, prev);
}

void* pf_hash_erase_num(pf_hash_t* hash, uint64_t key)
{
    struct pf_hash_node* cur  = NULL;
    struct pf_hash_node* prev = NULL;

    assert(hash);

    cur = find_num_impl(hash, key, &prev);
    if(cur == NULL)
    {
        pf_set_errno(PF_ENOKEY);
        return NULL;
    }

    return erase_impl(hash, key % hash->slot_size,cur, prev);
}

uint32_t pf_hash_count(const struct pf_hash* hash)
{
    assert(hash);

    return hash->value_count;
}

int pf_hash_clear(struct pf_hash* hash)
{
    uint32_t i                = 0;
    struct pf_hash_node* cur  = NULL;
    struct pf_hash_node* temp = NULL;

    assert(hash);

    for(i = 0; i < hash->slot_size; i++)
    {
        cur = hash->htable[i];
        while(cur)
        {
            temp = cur;
            cur = cur->next;
            free(temp);
        }

        hash->htable[i] = NULL;
    }
    hash->value_count = 0;

    return 0;
}

int32_t pf_hash_for_each(const struct pf_hash* hash,
                         void* arg,
                         int(*cb)(void* arg, void* key_ptr, uint64_t key_num, void* value))
{
    uint32_t i               = 0;
    int ret                  = 0;
    struct pf_hash_node* cur = NULL;

    assert(hash);
    assert(cb);

    for(i = 0; i < hash->slot_size; i++)
    {
        cur = hash->htable[i];
        while(cur)
        {
            if((ret = (*cb)(arg, cur->key.ptr, cur->key.num, cur->data)) != 0)
            {
                return ret;
            }
            cur = cur->next;
        }
    }
    return 0;
}

uint32_t pf_hash_BKDR_str(const void* value)
{
    uint32_t seed = 131; /* 31 131 1313 13131 131313 etc.. */
    uint32_t hash = 0;

    char* str =(char*)value;
    while(*str)
    {
        hash = hash * seed + (*str++);
    }

    return hash;
}

uint32_t pf_hash_DJB_str(const void* value)
{
    uint32_t hash = 5381;

    char* str = (char*)value;
    while(*str)
    {
        hash += (hash << 5) +(*str++);
    }

    return hash;
}

uint32_t pf_hash_SDBM_str(const void* value)
{
    uint32_t hash = 0;

    char* str = (char*)value;
    while(*str)
    {
        /* equivalent to: hash = 65599*hash +(*str++); */
        hash = (*str++) +(hash << 6) +(hash << 16) - hash;
    }

    return hash;
}

uint32_t pf_hash_PJW_str(const void* value)
{
    uint32_t BitsInUnignedInt = (uint32_t)(sizeof(uint32_t) * 8);
    uint32_t ThreeQuarters    = (uint32_t)((BitsInUnignedInt * 3) / 4);
    uint32_t OneEighth        = (uint32_t)(BitsInUnignedInt / 8);
    uint32_t HighBits         = (uint32_t)(0xFFFFFFFF) <<(BitsInUnignedInt - OneEighth);
    uint32_t hash             = 0;
    uint32_t test             = 0;

    char* str = (char*)value;
    while(*str)
    {
        hash =(hash << OneEighth) + (*str++);
        if((test = hash & HighBits) != 0)
        {
            hash = ((hash ^(test >> ThreeQuarters)) &(~HighBits));
        }
    }

    return hash;
}

uint32_t pf_hash_ELF_str(const void* value)
{
    uint32_t hash = 0;
    uint32_t x    = 0;

    char* str = (char*)value;
    while(*str)
    {
        hash = (hash << 4) +(*str++);
        if((x = hash & 0xF0000000L) != 0)
        {
            hash ^=(x >> 24);
            hash &= ~x;
        }
    }

    return hash;
}

/********************************************************************************************/

static inline uint32_t get_table_size(uint32_t size)
{
    int n = -1;
    static const uint32_t primes[] =
    {
        1, 3, 5, 11, 17, 37, 67, 131, 257, 521, 1031, 2053, 4099, 8209,
        16411, 32771, 65537, 131101, 262147, 524309, 1048583, 2097169,
        4194319, 8388617, 16777259, 33554467, 67108879, 134217757,
        268435459, 536870923, 1073741827, 2147483659, UINT32_MAX
    };

    if(size == 0) 
    {
        return 1;
    }

    n =(sizeof(uint32_t) * CHAR_BIT) -(__builtin_clz(size));

    return(primes[n - 1] >= size) ? primes[n - 1] : primes[n];
}

static inline struct pf_hash_node* find_num_impl(const struct pf_hash* hash, 
                                                 uint64_t key, 
                                                 struct pf_hash_node** prev)
{
    uint32_t hvalue = key % hash->slot_size;
    struct pf_hash_node* cur = hash->htable[hvalue];

    *prev = NULL;

    while(cur && key > cur->key.num)
    {
        *prev = cur;
        cur = cur->next;
    }

    if(cur && key != cur->key.num)
    {
        return NULL;
    }

    return cur;
}

static inline struct pf_hash_node* find_ptr_impl(const struct pf_hash* hash, 
                                                 void* key, 
                                                 struct pf_hash_node** prev)
{
    uint32_t hvalue = hash->hash_value(key) % hash->slot_size;
    struct pf_hash_node* cur = hash->htable[hvalue];

    *prev = NULL;

    while(cur && hash->key_cmp(key, cur->key.ptr) > 0)
    {
        *prev = cur;
        cur = cur->next;
    }

    if(cur && hash->key_cmp(key, cur->key.ptr) != 0)
    {
        return NULL;
    }

    return cur;
}

static inline int insert_impl(struct pf_hash* hash, 
                              uint64_t num, 
                              void* ptr, 
                              void* value, 
                              struct pf_hash_node* prev)
{
    uint32_t hvalue = num % hash->slot_size;
    struct pf_hash_node* newnode = malloc(sizeof(struct pf_hash_node));

    if(newnode == NULL)
    {
        pf_set_errno(PF_ENOMEM);
        return PF_ENOMEM;
    }

    if(ptr != NULL)
    {
        newnode->key.ptr = ptr;
    }
    else
    {
        newnode->key.num = num;
    }

    newnode->data = value;

    if(prev)
    {
        newnode->next = prev->next;
        prev->next = newnode;
    }
    else
    {
        newnode->next = hash->htable[hvalue];
        hash->htable[hvalue] = newnode;
    }

    hash->value_count++;

    return 0;
}

static inline void* erase_impl(struct pf_hash* hash, 
                               uint32_t hvalue,
                               struct pf_hash_node* cur, 
                               struct pf_hash_node* prev)
{
    void* data = NULL;

    /*first one */
    if(prev == NULL)
    {
        hash->htable[hvalue] = cur->next;
    }
    else  /*kick out of the list*/
    {
        prev->next = cur->next;
    }

    data = cur->data;
    free(cur);

    hash->value_count--;

    return data;
}

